home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / gxpath2.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  14.0 KB  |  520 lines
  1. /* Copyright (C) 1989, 1995, 1997, 1998, 1999 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: gxpath2.c,v 1.2 2000/09/19 19:00:39 lpd Exp $ */
  20. /* Path tracing procedures for Ghostscript library */
  21. #include "math_.h"
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gspath.h"        /* for gs_path_enum_alloc prototype */
  25. #include "gsstruct.h"
  26. #include "gxfixed.h"
  27. #include "gxarith.h"
  28. #include "gzpath.h"
  29.  
  30. /* Define the enumeration structure. */
  31. public_st_path_enum();
  32.  
  33. /* Read the current point of a path. */
  34. int
  35. gx_path_current_point(const gx_path * ppath, gs_fixed_point * ppt)
  36. {
  37.     if (!path_position_valid(ppath))
  38.     return_error(gs_error_nocurrentpoint);
  39.     /* Copying the coordinates individually */
  40.     /* is much faster on a PC, and almost as fast on other machines.... */
  41.     ppt->x = ppath->position.x, ppt->y = ppath->position.y;
  42.     return 0;
  43. }
  44.  
  45. /* Read the start point of the current subpath. */
  46. int
  47. gx_path_subpath_start_point(const gx_path * ppath, gs_fixed_point * ppt)
  48. {
  49.     const subpath *psub = ppath->current_subpath;
  50.  
  51.     if (!psub)
  52.     return_error(gs_error_nocurrentpoint);
  53.     *ppt = psub->pt;
  54.     return 0;
  55. }
  56.  
  57. /* Read the bounding box of a path. */
  58. /* Note that if the last element of the path is a moveto, */
  59. /* the bounding box does not include this point, */
  60. /* unless this is the only element of the path. */
  61. int
  62. gx_path_bbox(gx_path * ppath, gs_fixed_rect * pbox)
  63. {
  64.     if (ppath->bbox_set) {
  65.     /* The bounding box was set by setbbox. */
  66.     *pbox = ppath->bbox;
  67.     return 0;
  68.     }
  69.     if (ppath->first_subpath == 0) {
  70.     /* The path is empty, use the current point if any. */
  71.     int code = gx_path_current_point(ppath, &pbox->p);
  72.  
  73.     if (code < 0) {
  74.         /*
  75.          * Don't return garbage, in case the caller doesn't
  76.          * check the return code.
  77.          */
  78.         pbox->p.x = pbox->p.y = 0;
  79.     }
  80.     pbox->q = pbox->p;
  81.     return code;
  82.     }
  83.     /* The stored bounding box may not be up to date. */
  84.     /* Correct it now if necessary. */
  85.     if (ppath->box_last == ppath->current_subpath->last) {
  86.     /* Box is up to date */
  87.     *pbox = ppath->bbox;
  88.     } else {
  89.     fixed px, py, qx, qy;
  90.     const segment *pseg = ppath->box_last;
  91.  
  92.     if (pseg == 0) {    /* box is uninitialized */
  93.         pseg = (const segment *)ppath->first_subpath;
  94.         px = qx = pseg->pt.x;
  95.         py = qy = pseg->pt.y;
  96.     } else {
  97.         px = ppath->bbox.p.x, py = ppath->bbox.p.y;
  98.         qx = ppath->bbox.q.x, qy = ppath->bbox.q.y;
  99.     }
  100.  
  101. /* Macro for adjusting the bounding box when adding a point */
  102. #define ADJUST_BBOX(pt)\
  103.   if ((pt).x < px) px = (pt).x;\
  104.   else if ((pt).x > qx) qx = (pt).x;\
  105.   if ((pt).y < py) py = (pt).y;\
  106.   else if ((pt).y > qy) qy = (pt).y
  107.  
  108.     while ((pseg = pseg->next) != 0) {
  109.         switch (pseg->type) {
  110.         case s_curve:
  111.             ADJUST_BBOX(((const curve_segment *)pseg)->p1);
  112.             ADJUST_BBOX(((const curve_segment *)pseg)->p2);
  113.             /* falls through */
  114.         default:
  115.             ADJUST_BBOX(pseg->pt);
  116.         }
  117.     }
  118. #undef ADJUST_BBOX
  119.  
  120. #define STORE_BBOX(b)\
  121.   (b).p.x = px, (b).p.y = py, (b).q.x = qx, (b).q.y = qy;
  122.     STORE_BBOX(*pbox);
  123.     STORE_BBOX(ppath->bbox);
  124. #undef STORE_BBOX
  125.  
  126.     ppath->box_last = ppath->current_subpath->last;
  127.     }
  128.     return 0;
  129. }
  130.  
  131. /* Test if a path has any curves. */
  132. #undef gx_path_has_curves
  133. bool
  134. gx_path_has_curves(const gx_path * ppath)
  135. {
  136.     return gx_path_has_curves_inline(ppath);
  137. }
  138. #define gx_path_has_curves(ppath)\
  139.   gx_path_has_curves_inline(ppath)
  140.  
  141. /* Test if a path has no segments. */
  142. #undef gx_path_is_void
  143. bool
  144. gx_path_is_void(const gx_path * ppath)
  145. {
  146.     return gx_path_is_void_inline(ppath);
  147. }
  148. #define gx_path_is_void(ppath)\
  149.   gx_path_is_void_inline(ppath)
  150.  
  151. /* Test if a path has no elements at all. */
  152. bool
  153. gx_path_is_null(const gx_path * ppath)
  154. {
  155.     return gx_path_is_null_inline(ppath);
  156. }
  157.  
  158. /*
  159.  * Test if a subpath is a rectangle; if so, return its bounding box
  160.  * and the start of the next subpath.
  161.  * Note that this must recognize:
  162.  *      ordinary closed rectangles (M, L, L, L, C);
  163.  *      open rectangles (M, L, L, L);
  164.  *      rectangles closed with lineto (Mo, L, L, L, Lo);
  165.  *      rectangles closed with *both* lineto and closepath (bad PostScript,
  166.  *        but unfortunately not rare) (Mo, L, L, L, Lo, C).
  167.  */
  168. gx_path_rectangular_type
  169. gx_subpath_is_rectangular(const subpath * pseg0, gs_fixed_rect * pbox,
  170.               const subpath ** ppnext)
  171. {
  172.     const segment *pseg1, *pseg2, *pseg3, *pseg4;
  173.     gx_path_rectangular_type type;
  174.  
  175.     if (pseg0->curve_count == 0 &&
  176.     (pseg1 = pseg0->next) != 0 &&
  177.     (pseg2 = pseg1->next) != 0 &&
  178.     (pseg3 = pseg2->next) != 0
  179.     ) {
  180.     if ((pseg4 = pseg3->next) == 0 || pseg4->type == s_start)
  181.         type = prt_open;    /* M, L, L, L */
  182.     else if (pseg4->type != s_line)        /* must be s_line_close */
  183.         type = prt_closed;    /* M, L, L, L, C */
  184.     else if (pseg4->pt.x != pseg0->pt.x ||
  185.          pseg4->pt.y != pseg0->pt.y
  186.         )
  187.         return prt_none;
  188.     else if (pseg4->next == 0 || pseg4->next->type == s_start)
  189.         type = prt_fake_closed;    /* Mo, L, L, L, Lo */
  190.     else if (pseg4->next->type != s_line)    /* must be s_line_close */
  191.         type = prt_closed;    /* Mo, L, L, L, Lo, C */
  192.     else
  193.         return prt_none;
  194.     {
  195.         fixed x0 = pseg0->pt.x, y0 = pseg0->pt.y;
  196.         fixed x2 = pseg2->pt.x, y2 = pseg2->pt.y;
  197.  
  198.         if ((x0 == pseg1->pt.x && pseg1->pt.y == y2 &&
  199.          x2 == pseg3->pt.x && pseg3->pt.y == y0) ||
  200.         (x0 == pseg3->pt.x && pseg3->pt.y == y2 &&
  201.          x2 == pseg1->pt.x && pseg1->pt.y == y0)
  202.         ) {        /* Path is a rectangle.  Return the bounding box. */
  203.         if (x0 < x2)
  204.             pbox->p.x = x0, pbox->q.x = x2;
  205.         else
  206.             pbox->p.x = x2, pbox->q.x = x0;
  207.         if (y0 < y2)
  208.             pbox->p.y = y0, pbox->q.y = y2;
  209.         else
  210.             pbox->p.y = y2, pbox->q.y = y0;
  211.         while (pseg4 != 0 && pseg4->type != s_start)
  212.             pseg4 = pseg4->next;
  213.         *ppnext = (const subpath *)pseg4;
  214.         return type;
  215.         }
  216.     }
  217.     }
  218.     return prt_none;
  219. }
  220. /* Test if an entire path to be filled is a rectangle. */
  221. gx_path_rectangular_type
  222. gx_path_is_rectangular(const gx_path * ppath, gs_fixed_rect * pbox)
  223. {
  224.     const subpath *pnext;
  225.  
  226.     return
  227.     (gx_path_subpath_count(ppath) == 1 ?
  228.      gx_subpath_is_rectangular(ppath->first_subpath, pbox, &pnext) :
  229.      prt_none);
  230. }
  231.  
  232. /* Translate an already-constructed path (in device space). */
  233. /* Don't bother to update the cbox. */
  234. int
  235. gx_path_translate(gx_path * ppath, fixed dx, fixed dy)
  236. {
  237.     segment *pseg;
  238.  
  239. #define update_xy(pt)\
  240.   pt.x += dx, pt.y += dy
  241.     if (ppath->box_last != 0) {
  242.     update_xy(ppath->bbox.p);
  243.     update_xy(ppath->bbox.q);
  244.     }
  245.     if (path_position_valid(ppath))
  246.     update_xy(ppath->position);
  247.     for (pseg = (segment *) (ppath->first_subpath); pseg != 0;
  248.      pseg = pseg->next
  249.     )
  250.     switch (pseg->type) {
  251.         case s_curve:
  252. #define pcseg ((curve_segment *)pseg)
  253.         update_xy(pcseg->p1);
  254.         update_xy(pcseg->p2);
  255. #undef pcseg
  256.         default:
  257.         update_xy(pseg->pt);
  258.     }
  259. #undef update_xy
  260.     return 0;
  261. }
  262.  
  263. /* Scale an existing path by a power of 2 (positive or negative). */
  264. void
  265. gx_point_scale_exp2(gs_fixed_point * pt, int sx, int sy)
  266. {
  267.     if (sx >= 0)
  268.     pt->x <<= sx;
  269.     else
  270.     pt->x >>= -sx;
  271.     if (sy >= 0)
  272.     pt->y <<= sy;
  273.     else
  274.     pt->y >>= -sy;
  275. }
  276. void
  277. gx_rect_scale_exp2(gs_fixed_rect * pr, int sx, int sy)
  278. {
  279.     gx_point_scale_exp2(&pr->p, sx, sy);
  280.     gx_point_scale_exp2(&pr->q, sx, sy);
  281. }
  282. int
  283. gx_path_scale_exp2_shared(gx_path * ppath, int log2_scale_x, int log2_scale_y,
  284.               bool segments_shared)
  285. {
  286.     segment *pseg;
  287.  
  288.     gx_rect_scale_exp2(&ppath->bbox, log2_scale_x, log2_scale_y);
  289. #define SCALE_XY(pt) gx_point_scale_exp2(&pt, log2_scale_x, log2_scale_y)
  290.     SCALE_XY(ppath->position);
  291.     if (!segments_shared) {
  292.     for (pseg = (segment *) (ppath->first_subpath); pseg != 0;
  293.          pseg = pseg->next
  294.          )
  295.         switch (pseg->type) {
  296.         case s_curve:
  297.         SCALE_XY(((curve_segment *)pseg)->p1);
  298.         SCALE_XY(((curve_segment *)pseg)->p2);
  299.         default:
  300.         SCALE_XY(pseg->pt);
  301.         }
  302.     }
  303. #undef SCALE_XY
  304.     return 0;
  305. }
  306.  
  307. /*
  308.  * Reverse a path.  We know ppath != ppath_old.
  309.  * NOTE: in releases 5.01 and earlier, the implicit line added by closepath
  310.  * became the first segment of the reversed path.  Starting in release
  311.  * 5.02, the code follows the Adobe implementation (and LanguageLevel 3
  312.  * specification), in which this line becomes the *last* segment of the
  313.  * reversed path.  This can produce some quite unintuitive results.
  314.  */
  315. int
  316. gx_path_copy_reversed(const gx_path * ppath_old, gx_path * ppath)
  317. {
  318.     const subpath *psub = ppath_old->first_subpath;
  319.  
  320. #ifdef DEBUG
  321.     if (gs_debug_c('P'))
  322.     gx_dump_path(ppath_old, "before reversepath");
  323. #endif
  324.  nsp:
  325.     if (psub) {
  326.     const segment *prev = psub->last;
  327.     const segment *pseg;
  328.     segment_notes notes =
  329.         (prev == (const segment *)psub ? sn_none :
  330.          psub->next->notes);
  331.     segment_notes prev_notes;
  332.     int code;
  333.  
  334.     if (!psub->is_closed) {
  335.         code = gx_path_add_point(ppath, prev->pt.x, prev->pt.y);
  336.         if (code < 0)
  337.         return code;
  338.     }
  339.     /*
  340.      * The do ... while structure of this loop is artificial,
  341.      * designed solely to keep compilers from complaining about
  342.      * 'statement not reached' or 'end-of-loop code not reached'.
  343.      * The normal exit from this loop is the goto statement in
  344.      * the s_start arm of the switch.
  345.      */
  346.     do {
  347.         pseg = prev;
  348.         prev_notes = notes;
  349.         prev = pseg->prev;
  350.         notes = pseg->notes;
  351.         prev_notes = (prev_notes & sn_not_first) |
  352.         (notes & ~sn_not_first);
  353.         switch (pseg->type) {
  354.         case s_start:
  355.             /* Finished subpath */
  356.             if (psub->is_closed) {
  357.             code =
  358.                 gx_path_close_subpath_notes(ppath, prev_notes);
  359.             if (code < 0)
  360.                 return code;
  361.             }
  362.             psub = (const subpath *)psub->last->next;
  363.             goto nsp;
  364.         case s_curve:
  365.             {
  366.             const curve_segment *pc =
  367.             (const curve_segment *)pseg;
  368.  
  369.             code = gx_path_add_curve_notes(ppath,
  370.                                pc->p2.x, pc->p2.y,
  371.                                pc->p1.x, pc->p1.y,
  372.                     prev->pt.x, prev->pt.y, prev_notes);
  373.             break;
  374.             }
  375.         case s_line:
  376.             code = gx_path_add_line_notes(ppath,
  377.                     prev->pt.x, prev->pt.y, prev_notes);
  378.             break;
  379.         case s_line_close:
  380.             /* Skip the closing line. */
  381.             code = gx_path_add_point(ppath, prev->pt.x,
  382.                          prev->pt.y);
  383.             break;
  384.         default:    /* not possible */
  385.             return_error(gs_error_Fatal);
  386.         }
  387.     } while (code >= 0);
  388.     return code;        /* only reached if code < 0 */
  389.     }
  390. #undef sn_not_end
  391.     /*
  392.      * In the Adobe implementations, reversepath discards a trailing
  393.      * moveto unless the path consists only of a moveto.  We reproduce
  394.      * this behavior here, even though we consider it a bug.
  395.      */
  396.     if (ppath_old->first_subpath == 0 &&
  397.     path_last_is_moveto(ppath_old)
  398.     ) {
  399.     int code = gx_path_add_point(ppath, ppath_old->position.x,
  400.                      ppath_old->position.y);
  401.  
  402.     if (code < 0)
  403.         return code;
  404.     }
  405. #ifdef DEBUG
  406.     if (gs_debug_c('P'))
  407.     gx_dump_path(ppath, "after reversepath");
  408. #endif
  409.     return 0;
  410. }
  411.  
  412. /* ------ Path enumeration ------ */
  413.  
  414. /* Allocate a path enumerator. */
  415. gs_path_enum *
  416. gs_path_enum_alloc(gs_memory_t * mem, client_name_t cname)
  417. {
  418.     return gs_alloc_struct(mem, gs_path_enum, &st_path_enum, cname);
  419. }
  420.  
  421. /* Start enumerating a path. */
  422. int
  423. gx_path_enum_init(gs_path_enum * penum, const gx_path * ppath)
  424. {
  425.     penum->memory = 0;        /* path not copied */
  426.     penum->path = ppath;
  427.     penum->copied_path = 0;    /* not copied */
  428.     penum->pseg = (const segment *)ppath->first_subpath;
  429.     penum->moveto_done = false;
  430.     penum->notes = sn_none;
  431.     return 0;
  432. }
  433.  
  434. /* Enumerate the next element of a path. */
  435. /* If the path is finished, return 0; */
  436. /* otherwise, return the element type. */
  437. int
  438. gx_path_enum_next(gs_path_enum * penum, gs_fixed_point ppts[3])
  439. {
  440.     const segment *pseg = penum->pseg;
  441.  
  442.     if (pseg == 0) {        /* We've enumerated all the segments, but there might be */
  443.     /* a trailing moveto. */
  444.     const gx_path *ppath = penum->path;
  445.  
  446.     if (path_last_is_moveto(ppath) && !penum->moveto_done) {    /* Handle a trailing moveto */
  447.         penum->moveto_done = true;
  448.         penum->notes = sn_none;
  449.         ppts[0] = ppath->position;
  450.         return gs_pe_moveto;
  451.     }
  452.     return 0;
  453.     }
  454.     penum->pseg = pseg->next;
  455.     penum->notes = pseg->notes;
  456.     switch (pseg->type) {
  457.     case s_start:
  458.         ppts[0] = pseg->pt;
  459.         return gs_pe_moveto;
  460.     case s_line:
  461.         ppts[0] = pseg->pt;
  462.         return gs_pe_lineto;
  463.     case s_line_close:
  464.         ppts[0] = pseg->pt;
  465.         return gs_pe_closepath;
  466.     case s_curve:
  467. #define pcseg ((const curve_segment *)pseg)
  468.         ppts[0] = pcseg->p1;
  469.         ppts[1] = pcseg->p2;
  470.         ppts[2] = pseg->pt;
  471.         return gs_pe_curveto;
  472. #undef pcseg
  473.     default:
  474.         lprintf1("bad type %x in gx_path_enum_next!\n", pseg->type);
  475.         return_error(gs_error_Fatal);
  476.     }
  477. }
  478.  
  479. /* Return the notes from the last-enumerated segment. */
  480. segment_notes
  481. gx_path_enum_notes(const gs_path_enum * penum)
  482. {
  483.     return penum->notes;
  484. }
  485.  
  486. /* Back up 1 element in the path being enumerated. */
  487. /* Return true if successful, false if we are at the beginning of the path. */
  488. /* This implementation allows backing up multiple times, */
  489. /* but no client currently relies on this. */
  490. bool
  491. gx_path_enum_backup(gs_path_enum * penum)
  492. {
  493.     const segment *pseg = penum->pseg;
  494.  
  495.     if (pseg != 0) {
  496.     if ((pseg = pseg->prev) == 0)
  497.         return false;
  498.     penum->pseg = pseg;
  499.     return true;
  500.     }
  501.     /* We're at the end of the path.  Check to see whether */
  502.     /* we need to back up over a trailing moveto. */
  503.     {
  504.     const gx_path *ppath = penum->path;
  505.  
  506.     if (path_last_is_moveto(ppath) && penum->moveto_done) {        /* Back up over the trailing moveto. */
  507.         penum->moveto_done = false;
  508.         return true;
  509.     } {
  510.         const subpath *psub = ppath->current_subpath;
  511.  
  512.         if (psub == 0)    /* empty path */
  513.         return false;
  514.         /* Back up to the last segment of the last subpath. */
  515.         penum->pseg = psub->last;
  516.         return true;
  517.     }
  518.     }
  519. }
  520.